package com.sanra;


import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Random;

public class Sort {

    public static void main(String[] args) {
//        insertSort();
//        shellSort();
//        merge();
//        mergeSort();
//        quickSort();
        quickSortFromWeb();
//        countSort();
//        radixSortFromWeb();
//        game();
    }

    ///冒泡排序
    static void mpSort() {
        System.out.println("冒泡排序");
        int[] arr = {5, 3, 6, 8, 1, 7, 9, 4, 2};
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        print(arr);
    }

    ///选择排序
    /// 先依次选 i 然后拿 i 索引值和后面所有值做对比 若发现小于的则交换  否则继续下一个
    static void selectSort() {
        System.out.println("选择排序");

        int[] arr = {5, 3, 6, 8, 1, 7, 9, 4, 2};
        System.out.println("初始状态：");
        print(arr);

        for (int i = 0; i < arr.length; i++) {
            int minPos = i;

            for (int j = i + 1; j < arr.length; j++) {
                minPos = arr[j] < arr[minPos] ? j : minPos;
            }
            System.out.println("minPos :" + minPos);
            swap(arr, i, minPos);
            System.out.println("经过" + i + "次循环之后，数组内容：");
            print(arr);
        }
    }

    ///插入排序
    /// 取 i 索引  再拿i索引前的两两比较 若前小于后则交换
    static void insertSort() {
        System.out.println("InsertSort");
        int[] arr = {9, 3, 1, 4, 6, 8, 7, 5, 2};
        print(arr);
        System.out.println("");
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j > 0; j--) {
                if (arr[j] < arr[j - 1]) {
                    swap(arr, j, j - 1);
                }
            }
        }
        print(arr);
        System.out.println("");
    }

    ///卡步子排序，先跨大步，跨完一遍，再重头跨小步，如此反复，步子为1时  走完一遍就排好了
    ///希尔排序
    ///先计算一个小数组标准，然后以这个标准，从大数组开始遍历，一直到小数组的末尾和大数组末尾重合，则重新计算数组大小标准，数组标准一直在缩小中
    static void shellSort() {
        System.out.println("shellSort");
        int[] arr = {9, 6, 11, 3, 5, 12, 8, 7, 10, 15, 14, 4, 1, 13, 2};
        print(arr);
        System.out.println(arr.length);
        int h = 1;
        while (h <= arr.length / 3) {
            h = h * 3 + 1;
        }
        ///计算一个偏后的一个位置
        System.out.println("h=======" + h);
        ///控制小数组的大小，当大小等于1是就成了相邻两个交换了
        ///每次step用完了就缩小 缩小方法是  当前step的 三分之一 缩小完后再对数组从头开始 跨step个位置开始遍历交换
        for (int step = h; step > 0; step = (step - 1) / 3) {
//            System.out.println("step ====> " + step);
            ///控制小数组区域向完整数组的右侧流动
            for (int i = step; i < arr.length; i++) {
//                System.out.println("i ====> " + i);
                ////小段数组的地位，
                for (int j = i; j > step - 1; j -= step) {
//                    System.out.println("j ====> " + j);
                    if (arr[j] < arr[j - step]) {
                        swap(arr, j, j - step);
                        print(arr);
                    }
                }
            }
        }
        print(arr);
        System.out.println("");
    }

    public static void shellSortFromWeb() {
        System.out.println("shellSortFromWeb");
        int[] arr = {9, 6, 11, 3, 5, 12, 8, 7, 10, 15, 14, 4, 1, 13, 2, 16};
        print(arr);
        int h = 1;
        while (h <= arr.length / 3) {
            h = h * 3 + 1;
        }
        System.out.println(arr.length);
        System.out.println("h=======" + h);

        int length = arr.length;
        int temp;

        for (int step = length / 2; step >= 1; step /= 2) {
            for (int i = step; i < length; i++) {
                temp = arr[i];
                int j = i - step;
                while (j > 0 && arr[j] > temp) {
                    arr[j + step] = arr[j];
                    j -= step;
                }
                arr[j + step] = temp;
            }
        }
    }

    ///归并排序
    ///对数组分组 分到每组只有2个的时候  对每组内数据比较大小， 再合并一个小组 与另外一个小组 分别做比较，这样先比较 再合并 ，再比较再合并，反复进行即可完成。
    static void mergeSort() {
        int[] arr = {9, 6, 11, 3, 5, 12, 8, 7, 10, 15, 14, 4, 1, 13, 2};
        mergeSort(arr, 0, arr.length - 1);
        print(arr);
    }

    static void mergeSort(int[] arr, int low, int high) {
        int mid = (low + high) / 2;
        if (low < high) {
            mergeSort(arr, low, mid);
            mergeSort(arr, mid + 1, high);
            mergeSort(arr, low, mid, high);
        }
    }

    static void mergeSort(int[] arr, int low, int mid, int high) {
        int[] temp = new int[high - low + 1];
        int i = low;
        int j = mid + 1;
        int k = 0;

        while (i <= mid && j <= high) {
            temp[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
        }

        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        while (j <= high) {
            temp[k++] = arr[j++];
        }
        if (temp.length >= 0) System.arraycopy(temp, 0, arr, low, temp.length);
    }


    ///快速排序
    ///找个参考值作为判断依据，左指针右移，右指针左移，找到左指针值比参考值小的和右指针值比参考值大的，这是这俩值相互交换位置，当左指针大于右指针，则两个交换，反之则两边指针继续向中间移动
    static void quickSort() {
        int[] arr = {9, 6, 11, 3, 5, 12, 8, 7, 10, 15, 14, 4, 1, 13, 2};
        print(arr);
        quickSort(arr, 0, arr.length - 1);
        print(arr);
    }

    static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int mid = partition(arr, low, high);
            quickSort(arr, low, mid - 1);
            quickSort(arr, mid + 1, high);
        }
    }

    static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int left = low;
        int right = high - 1;
        while (left <= right) {
            while (left <= right && arr[left] <= pivot) left++;
            while (left <= right && arr[right] > pivot) right--;
            if (left < right) swap(arr, left, right);
        }
        swap(arr, left, high);
        return left;
    }

    ///根据中轴位置取出轴数值，左边大于中轴放右边，右边小于中轴放左边，如此反复，即可
    ///先从右往左找小于轴的，找到后停止，把当前值放到最左边界，
    ///再从左向右找大于轴的，找到后停止，把当前为放到最右边界，
    ///一圈完后，把中轴放入低位指向位置，一轮结束
    ///这时 把低位当做新一轮排序的中轴取值位置
    static void quickSortFromWeb() {
        int[] arr = {9, 6, 11, 3, 5, 12, 8, 7, 10, 15, 14, 4, 1, 13, 2};
        print(arr);
        quickSortFromWeb(arr, 0, arr.length - 1);
        print(arr);
    }

    static void quickSortFromWeb(int[] arr, int low, int high) {
        if (low >= high) return;
        int mid = get_mid(arr, low, high);
        quickSortFromWeb(arr, low, mid - 1);
        quickSortFromWeb(arr, mid + 1, high);
    }

    static int get_mid(int[] arr, int low, int high) {
        int pivot = arr[low];
        System.out.println("中轴值是多少" + low + "[" + pivot + "]");
        while (low < high) {
            while (low < high && arr[high] >= pivot) high--;
            System.out.println();
            print(arr);
            System.out.println("右边小于中轴左交换：" + high + "[" + arr[high] + "] --- > " + low + "[" + arr[low] + "]");
            arr[low] = arr[high];
            print(arr);
            while (low < high && arr[low] <= pivot) low++;
            System.out.println();
            print(arr);
            System.out.println("左边小于中轴右交换" + low + "[" + arr[low] + "] --- > " + high + "[" + arr[high] + "]");
            arr[high] = arr[low];
            print(arr);
        }
        System.out.println("中轴值放置" + pivot + " --- > " + low);
        arr[low] = pivot;
        print(arr);
        return low;
    }


    ///计数排序
    ///数据特点是多且重复，就是统计排序，给每个计数桶中放置元素
    static void countSort() {
        int[] arr = new int[1000];
        Random random = new Random();
        for (int i = 0; i < 1000; i++) {
            arr[i] = random.nextInt(20);
        }
        int[] res = countSort(arr); //非稳定计数排序
//        int[] res = stableCountSort(arr); //稳定计数排序
        System.out.println(Arrays.toString(res));
    }

    static int[] countSort(int[] arr) {
        int min = findMin(arr);
        int max = findMax(arr);
        int bucketLen = max + 1 - min;
        int[] bucket = new int[bucketLen];

        for (int value : arr) {
            bucket[value]++;
        }
        System.out.println(Arrays.toString(bucket));

        int sortedIndex = 0;
        for (int i = 0; i < bucket.length; i++) {
            for (int j = bucket[i]; j > 0; j--) {
                arr[sortedIndex++] = i;
            }
        }
        return arr;
    }

    ///稳定桶排序
    ///先给桶放好数量，再把桶计数累加计算存储，再对原数组逆序排到新数组中
    static int[] stableCountSort(int[] arr) {
        int min = findMin(arr);
        int max = findMax(arr);
        int bucketLen = max + 1 - min;
        int[] res = new int[arr.length];
        int[] count = new int[bucketLen];

        for (int value : arr) {
            count[value]++;
        }
        print(count);

        for (int i = 1; i < count.length; i++) {
            count[i] = count[i] + count[i - 1];
        }
        print(count);

        for (int i = arr.length - 1; i >= 0; i--) {
            int arrValue = arr[i]; //逆序找到原数组的一个值，再桶中找到他的位置，对桶元素-1表示从桶中拿出来一个值，再放到逆序新数组的前一位，这样就排好了
            res[--count[arrValue]] = arrValue;
        }
        return res;
    }

    static int findMin(int[] arr) {
        int minValue = arr[0];
        for (int value : arr) {
            if (minValue > value) {
                minValue = value;
            }
        }
        return minValue;
    }

    static int findMax(int[] arr) {
        int maxValue = arr[0];
        for (int value : arr) {
            if (maxValue < value) {
                maxValue = value;
            }
        }
        return maxValue;
    }

    ///基数排序
    ///从个位到高位依次比较排序
    ///比较适合 数据范围比较大的数组排序
    static void radixSortFromWeb() {
        int count = 10;
        int[] arr = new int[count];
        Random random = new Random();
        for (int i = 0; i < count; i++) {
            arr[i] = random.nextInt(200000);
        }
        print(arr);
        int maxDigit = getMaxDigit(arr);
//        int[] res = radixSortFromWeb(arr, maxDigit);
        int[] res = radixFromLearning(arr, maxDigit);
        print(res);
    }

    /**
     * 获取最高位数
     */
    static int getMaxDigit(int[] arr) {
        int maxValue = getMaxValue(arr);
        return getNumLength(maxValue);
    }

    static int getMaxValue(int[] arr) {
        int maxValue = arr[0];
        for (int value : arr) {
            if (maxValue < value) {
                maxValue = value;
            }
        }
        return maxValue;
    }

    static int getNumLength(long num) {
        if (num == 0) {
            return 1;
        }
        int lenght = 0;
        for (long temp = num; temp != 0; temp /= 10) {
            lenght++;
        }
        return lenght;
    }

    static int[] radixSortFromWeb(int[] arr, int maxDigit) {
        int mod = 10;
        int dev = 1;

        for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
            // 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)
            int[][] counter = new int[mod * 2][0];
            for (int item : arr) {
                int bucket = ((item % mod) / dev) + mod;
                counter[bucket] = arrayAppend(counter[bucket], item);
            }
            int pos = 0;
            for (int[] bucket : counter) {
                for (int value : bucket) {
                    arr[pos++] = value;
                }
            }
        }
        return arr;
    }

    /**
     * 自动扩容，并保存数据
     */
    static int[] arrayAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }

    static int[] radixFromLearning(int[] arr, int maxDigit) {
        int[] res = new int[arr.length];
        int[] count = new int[10];

        for (int i = 0; i < maxDigit; i++) {
            int div = (int) Math.pow(10, i);
            for (int value : arr) {
                int num = value / div % 10;
                count[num]++;
            }
            for (int m = 1; m < count.length; m++) {
                count[m] = count[m] + count[m - 1];
            }

            for (int n = arr.length - 1; n >= 0; n--) {
                int num = arr[n] / div % 10;
                res[--count[num]] = arr[n];
            }
            System.arraycopy(res, 0, arr, 0, arr.length);
            Arrays.fill(count, 0);
        }
        return res;
    }

    static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        System.out.println(i + " <-------------> " + j);
        print(arr);
    }

    static void print(int[] arr) {
        for (int a : arr) {
            System.out.print(a + " ");
        }
        System.out.println();
    }

    static void game() {
        String[] arr = {"a", "b", "c", "d", "e", "f"};
        ArrayDeque<String> queue = new ArrayDeque<>(Arrays.asList(arr));
        while (queue.size() > 1) {
            for (int i = 0; i < 6; i++) {
                String k = queue.removeFirst();
                queue.addLast(k);
                System.out.println(queue.toString());
            }
            String s = queue.removeFirst();
            System.out.println(s + "被淘汰");
        }
        System.out.println(queue.removeLast() + "获胜");
    }
}
